package com.wkh.datastructure;

import java.util.Arrays;

//斐波那契数列
public class Fibonacci {
    public static int fibonacci(int n){
        int[] cache = new int[n+1];
        Arrays.fill(cache,-1);
        cache[0] = 0;
        cache[1] = 1;
        return f(n,cache);
    }
    private static int f(int n,int[] array){
        /*if (n == 0){
            return 0;
        }
        if (n == 1){
            return 1;
        }*/
        if (array[n] != -1){
            return array[n];
        }
        array[n] = f(n-1,array)+f(n-2,array);
        return array[n];
    }

    public static void main(String[] args) {
        int f = fibonacci(4);
        System.out.println(f);
    }
}
